package com.搜索和回溯;


class Solution5 {

    public int movingCount(int m, int n, int k) {
        int num=0;//记录可到达格子数量
        int[][] g=new int[m][n];
        num=dfs(g,0,0,k,num);
        return num;
    }
    int dfs(int[][] g,int i,int j,int k,int num){
        int i1=i/10,i2=i%10;
        int j1=j/10,j2=j%10;
        if(i<0||i>g.length-1||j<0||j>g[0].length-1||(i1+i2+j1+j2)>k||g[i][j]==1) return num;
        //递推开始
        num++;
        //将该单元格标记为已经访问,0表示未被访问，1表示已经被访问。
        g[i][j]=1;
        //递归其上下左右单元格
        num=dfs(g,i-1,j,k,num);
        num=dfs(g,i+1,j,k,num);
        num=dfs(g,i,j+1,k,num);
        num=dfs(g,i,j-1,k,num);
        return num;
    }
}

public class 剑指Offer13机器人的运动范围 {
    public static void main(String[] args) {
        Solution5 s=new Solution5();
        System.out.println(s.movingCount(2, 3, 1));
    }
}
